package com.example.leetcode.solution;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution726 {
    public static void main(String[] args) {
//        String s = new Solution726().countOfAtoms("J3(Ker23(HWR)32)123((N42)24(OB40Li30CHe3O48LiNN26)33(C12Li48N30H13HBe31)21(BHN30Li26BCBe47N40)15(H5)16)14");
//        String s = new Solution726().countOfAtoms("(H2O2)3");
        String s = new Solution726().countOfAtoms("Mg(OH)2");
//        String s = new Solution726().countOfAtoms("K4(ON(SO3)2)2");
//        String s = new Solution726().countOfAtoms("(((U42Se42Fe10Mc31Rh49Pu49Sb49)49V39Tm50Zr44Og6)33((W2Ga48Tm14Eu46Mt12)23(RuRnMn11)7(Yb15Lu34Ra19CuTb2)47(Md38BhCu48Db15Hf12Ir40)7CdNi21(Db40Zr24Tc27SrBk46Es41DsI37Np9Lu16)46(Zn49Ho19RhClF9Tb30SiCuYb16)15)37(Cr48(Ni31)25(La8Ti17Rn6Ce35)36(Sg42Ts32Ca)37Tl6Nb47Rh32NdGa18Cm10Pt49(Ar37RuSb30Cm32Rf28B39Re7F36In19Zn50)46)38(Rh19Md23No22PoTl35Pd35Hg)41)50");
//        String s = new Solution726().countOfAtoms("((Md16Cm19HfNe47K29(NeW42ZrPd9)17Ag7Ar6P9HsFr18Ar18O31Tc5Md42(W6Sn5Er29SB40Ho42Co31Si42)44)7(La24Au2Bh12MoFr11LaHf24Re13Bh20Sc2)41(Tb33BLi14Al35Cu14)9Rh5Tl(Cr3SNd20Fe)14B27Cf48H11Sb8Sb25HsRhCm40(Fe4Cs13At49)26((Co6RnMg15Be30Hs9)40(Rg43SNoCn29F)2(Md25DbMn27Ni41)22(Ac28Pu50PdHoNa50)40(Fm28B15In)16(Pb41PmHf24Zn4Ts39Np25Tl47Lu47)6(Ru3Ni20Sm35)16(Ru23RaAt5Cs15Ga)8(Ra26Sb16Cr44Ds25Ar23Pm34C49)6)41(ThBSc15W(Nh12Li42Ts5Sr11Mn2Ga22W3)40(Bh50No12Zr43Mo18As18Sc17Ti17Ca28Tc50)11)6(Pr(Sb46Dy14Fe11)42(Cd14AlPd28Li13Sm4Fm50F33Ti)38(Bk14Fl50)31)4(N18Am45Cl36(Pr32Ta3Am)39Th36Si50NiDsEr50Am8Co25Pu24Ts17Ge37Ce36Re10TcSnWZn38No35Ar18Rf33P8(La5)7(Lr43Sg40)36(Au12HfCr10Fr40)37)9((Mn15Co20U9)5LvRb48LrLv37No(Pt20Tl44Nd31Cu32Ga19Lu4Es35)29(Po47Te47Na29Nh48VF28O28Ti46Cu28)45(Co8Bh5)20)43)35");
        System.out.println(s);
    }

    public String countOfAtoms(String formula) {
        Map<String, Integer> groupMap = new HashMap<>();
        group(formula, groupMap, null);

        Map<String, Integer> groupMap2 = new HashMap<>();
        groupMap.forEach((key, value) -> {
            group2(key, groupMap2, value);
        });

        Map<String, Integer> resultMap = new HashMap<>();
        groupMap2.entrySet().forEach(entry -> {
            count(entry.getKey(), resultMap, entry.getValue());
        });
        Map<String, Integer> resultMap2 = new HashMap<>();
        resultMap.entrySet().forEach(entry -> {
            count2(entry.getKey(), resultMap2, entry.getValue());
        });
        StringBuffer stringBuffer = new StringBuffer();
        resultMap2.keySet().stream().sorted().forEach(s -> {
            stringBuffer.append(s);
            if (resultMap2.get(s) > 1) {
                stringBuffer.append(resultMap2.get(s));
            }
        });
        return stringBuffer.toString();
    }

    /**
     * \\((([A-Z][a-z]*)*\\d*\\((([A-Z][a-z]*)+\\d*)*\\)\\d*)*\\)\\d+
     * \\((([A-Z][a-z]*)+\\d*)*\\)\\d*
     *
     * @param formula
     * @param groupMap
     */
    public List<String> group(String formula, Map<String, Integer> groupMap, List<String> groupList) {
        String reg = "\\((([A-Z][a-z]*)*\\d*(\\((([A-Z][a-z]*)+\\d*)*\\)\\d*)*)*\\)\\d+";
        Pattern pattern = Pattern.compile(reg);
        Matcher matcher = pattern.matcher(formula);
        if (groupList == null) {
            groupList = new ArrayList<>();
        }
        List<String> temp = new ArrayList<>();
        while (matcher.find()) {
            String group = matcher.group();
            temp.add(group);
        }
        if (temp.size() == 0) {
            groupMap.put(formula, 1);
            return groupList;
        }

        for (String s : temp) {
            formula = formula.replace(s, "");
        }
        int times = 1;
        if (formula.contains(")")) {
            String num = formula.substring(formula.lastIndexOf(")") + 1);
            if(num.matches("\\d+")){
                times = Integer.valueOf(num);
            }
        }
        for (String s : temp) {
            groupMap.put(s, times);
        }
        groupMap.put(formula, 1);
        return groupList;
    }

    public void group2(String formula, Map<String, Integer> groupMap, int times) {
        String reg = "\\((([A-Z][a-z]*)+\\d*)*\\)\\d*";
        Pattern pattern = Pattern.compile(reg);
        Matcher matcher = pattern.matcher(formula);
        List<String> temp = new ArrayList<>();
        while (matcher.find()) {
            String group = matcher.group();
            temp.add(group);
        }
        if (temp.size() == 0) {
            groupMap.put(formula, times);
            return;
        }
        for (String s : temp) {
            formula = formula.replace(s, "");
        }
        int t = times;
        if (formula.contains(")")) {
            String num = formula.substring(formula.lastIndexOf(")") + 1);
            if(num.matches("\\d+")){
                t *= Integer.valueOf(num);
            }
        }
        for (String s : temp) {
            groupMap.put(s, t);
        }
        groupMap.put(formula, times);
    }

    public void count(String formula, Map<String, Integer> groupMap, int times) {
        String reg = "(([A-Z][a-z]*)+\\d*)+";
        Pattern pattern = Pattern.compile(reg);
        Matcher matcher = pattern.matcher(formula);
        List<String> groupList = new ArrayList<>();
        while (matcher.find()) {
            String group = matcher.group();
            groupList.add(group);
        }
        for (String s : groupList) {
            formula = formula.replace(s, "");
        }
        if (formula.contains(")")) {
            String num = formula.substring(formula.lastIndexOf(")") + 1);
            if(num.matches("\\d+")){
                times *= Integer.valueOf(num);
            }
        }
        for (String s : groupList) {
            Integer integer2 = groupMap.get(s);
            if (integer2 == null) integer2 = 0;
            groupMap.put(s, times + integer2);
        }
    }

    public void count2(String formula, Map<String, Integer> groupMap, int times) {
        String reg = "[A-Z][a-z]*\\d*";
        Pattern pattern = Pattern.compile(reg);
        Matcher matcher = pattern.matcher(formula);
        List<String> groupList = new ArrayList<>();
        while (matcher.find()) {
            String group = matcher.group();
            groupList.add(group);
        }
        for (String s : groupList) {
            formula = formula.replace(s, "");
        }
        for (String s : groupList) {
            String reg2 = "\\d+";
            Pattern pattern2 = Pattern.compile(reg2);
            Matcher matcher2 = pattern2.matcher(s);
            int t = times;
            if (matcher2.find()) {
                String group = matcher2.group();
                t *= Integer.valueOf(group);
                s = s.replace(group, "");
            }

            Integer integer2 = groupMap.get(s);
            if (integer2 == null) integer2 = 0;
            groupMap.put(s, t + integer2);
        }
    }
}
